use std::collections::HashMap;
use std::collections::VecDeque;

type Coord = (i32, i32);

fn adjacents(&(x, y): &Coord) -> [Coord; 4] {
    [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
}

#[derive(Default)]
struct Graph {
    risk_level: HashMap<Coord, i32>,
    row: i32,
    col: i32,
}

impl Graph {
    fn in_range(&self, &(x, y): &Coord) -> bool {
        x >= 0 && x < self.col && y >= 0 && y < self.row
    }
}


fn parse_input() -> Graph {
    let input = std::fs::read_to_string("./day15/input.txt").unwrap();
    let mut graph = Graph::default();
    for (y, line) in input.lines().enumerate() {
        for (x, ch) in line.chars().enumerate() {
            graph.risk_level.insert((x as i32, y as i32), ch.to_digit(10).unwrap() as i32);
        }
    }
    graph.row = input.lines().count() as i32;
    graph.col = input.lines().nth(0).unwrap().chars().count() as i32;
    graph
}

fn shortest_risk(graph: &Graph) -> i32 {
    let target_coord = (graph.col - 1, graph.row - 1);

    // Dij shortest path
    let mut lowest_risk: HashMap<Coord, i32> = HashMap::new();
    let mut queue: VecDeque<Coord> = VecDeque::new();
    queue.push_back((0, 0));
    lowest_risk.insert((0, 0), 0);
    
    loop {
        match queue.pop_front() {
            None => break,
            Some(coord) => {
                let &coord_rick = lowest_risk.get(&coord).unwrap();
                for adj_coord in adjacents(&coord) {
                    if !graph.in_range(&adj_coord) {
                        continue;
                    }
                    let new_rick = coord_rick + graph.risk_level.get(&adj_coord).unwrap();

                    let rick = lowest_risk.entry(adj_coord).or_insert(i32::MAX);
                    if *rick > new_rick {
                        *rick = new_rick;
                        queue.push_back(adj_coord);
                    }
                }
            }
        }
    }

    *lowest_risk.get(&target_coord).unwrap()
}

#[allow(unused)]
fn part1(graph: &Graph) {
    println!("Part1: {}", shortest_risk(graph));
}

#[allow(unused)]
fn part2(graph: &Graph) {
    // Expend Graph
    let mut risk_level = HashMap::new();
    for ((x, y), risk) in graph.risk_level.iter() {
        for dx in 0..5 {
            for dy in 0..5 {
                risk_level.insert(
                    (x + dx * graph.col, y + dy * graph.row),
                    (risk + dx + dy - 1) % 9 + 1
                );
            }
        }
    }

    let graph = Graph {
        risk_level: risk_level,
        row: graph.row * 5,
        col: graph.col * 5
    };
    
    println!("Part2: {}", shortest_risk(&graph));
}

fn main() {
    let graph = parse_input();
    part1(&graph);
    part2(&graph);
}
